Astmatyk

To zadanie pochodzi z Kółka Informatycznego w Staszicu.

autor: Piotr Cerobski

Bajtazar jest miłośnikiem wycieczek górskich. Niestety cierpi na astmę i gdy wejdzie na zbyt dużą wysokość to zaczyna się dusić. Z tego powodu musi bardzo dokładnie planować swoje wyprawy. Jednak nie jest to proste. Bajtazar posiada bardzo dokładne mapy gór z dziesiątkami tysięcy szlaków, każdy szlak zaczyna się na pewnej wysokości i na jakiejś kończy. Nasz bohater ustalił miejsce skąd wyrusza i dokąd się kieruje jednak przytłoczony ilością informacji za bardzo sobie nie radzi z ułożeniem optymalnej trasy.

Zadanie

Pomóż Bajtazarowi w ułożeniu wycieczki. Napisz program który wczyta opis gór (punkty na różnych wysokościach połączone szlakami) i powie na jaką minimalną wysokość musi wejść Bajtazar aby dojść do wyznaczonego miejsca.

Wejście

W pierwszym wierszu znajdują się liczby N i M (1<=N<=100000; 1<=M<=300000), które oznaczają odpowiednio ilość punktów na mapie i ilość szlaków. W następnych N wierszach znajdują się wysokości na których leżą punkty. Wysokości to liczby całkowite z przedziału 1..1000000. W K+1 wierszu znajduje się wysokość K-tego wierzchołka. W każdym z następnych M wierszy znajduje się opis szlaku. Składa się on z dwóch liczb A B, które mówią, iż szlak ten prowadzi od punktu A do punktu B. Po szlakach można chodzić w obie strony i można założyć że wysokość, na której leży szlak mieści się między wysokością A i B.

Wyjście

Twój program powinien wypisać minimalną wysokość, na którą musi wejść Bajtazar, aby przejść po szlakach z wierzchołka 1 do wierzchołka n. Możesz założyć, że jakaś droga zawsze istnieje.

Przykład

Dla danych wejściowych:

9 11
3
10
9
6
8
3
2
4
1
1 2
1 3
7 1
4 1
4 6
5 3
6 7
7 8
8 9
6 9
5 9

program powinien wypisać liczbę:

3

(jest to droga 1-7-6-9)